#define _CRT_SECURE_NO_WARNINGS

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (head == nullptr || head->next == nullptr)
            return head;
        ListNode* prev = nullptr;
        ListNode* cur = head;
        ListNode* next = head;
        while (cur && cur->next)
        {
            next = cur->next;
            if (prev == nullptr)
                head = next;
            else
                prev->next = next;
            cur->next = next->next;
            next->next = cur;
            prev = cur;
            cur = cur->next;
        }
        return head;
    }
};

class Solution {
public:
    void _swapR(ListNode*& head, ListNode* prev, ListNode* cur, ListNode* next)
    {
        if (cur == nullptr || cur->next == nullptr)
            return;
        _swapR(head, cur->next, cur->next->next, next);
        next = cur->next;
        if (prev == nullptr)
            head = next;
        else
            prev->next = next;
        cur->next = next->next;
        next->next = cur;
        return;
    }

    ListNode* swapPairs(ListNode* head) {
        if (head == nullptr || head->next == nullptr)
            return head;
        _swapR(head, nullptr, head, head);
        return head;
    }
};

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* slow = head;
        ListNode* fast = head;
        for (int i = 0; i < n; i++)
            fast = fast->next;
        if (fast == nullptr)
        {
            ListNode* tmp = slow;
            head = slow->next;
            delete tmp;
            return head;
        }
        while (fast->next)
        {
            slow = slow->next;
            fast = fast->next;
        }
        ListNode* tmp = slow->next;
        slow->next = tmp->next;
        delete tmp;
        return head;
    }
};

class Solution {
public:
    int getListNum(ListNode* root)
    {
        int num = 0;
        while (root)
        {
            root = root->next;
            num++;
        }
        return num;
    }

    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
        int NA = getListNum(headA);
        int NB = getListNum(headB);
        int gap = abs(NA - NB);
        ListNode* more = headA;
        ListNode* less = headB;
        if (NA < NB)
        {
            less = headA;
            more = headB;
        }
        for (int i = 0; i < gap; i++)
        {
            more = more->next;
        }
        while (less != nullptr && more != nullptr && more != less)
        {
            more = more->next;
            less = less->next;
        }
        return more;
    }
};

class Solution {
public:
    ListNode* detectCycle(ListNode* head) {
        set<ListNode*> s;
        ListNode* cur = head;
        while (cur)
        {
            if (s.find(cur) != s.end())
                return cur;
            s.insert(cur);
            cur = cur->next;
        }
        return nullptr;
    }
};

class Solution {
public:
    ListNode* detectCycle(ListNode* head) {
        ListNode* cur = head;
        ListNode* fast = head;
        int fastnum = 0;
        ListNode* slow = head;
        int slownum = 0;
        while (fast && fast->next && fast->next->next)
        {
            fast = fast->next->next;
            fastnum += 2;
            slow = slow->next;
            slownum++;
            if (slow == fast)
            {
                while (cur != fast)
                {
                    cur = cur->next;
                    fast = fast->next;
                }
                return cur;
            }
        }
        return nullptr;
    }
};